Computer programming is an art, because it applies accumulated knowledge to the world, because it requires skill and ingenuity, and especially because it produces objects of beauty. A programmer who subconsciously views himself as an artist will enjoy what he does and will do it better.
— Donald Knuth

序

雖然市面上已經有很多很棒的演算法的教材及參考書，
但我的目標在於寫出平易近人的競賽程式設計入門書及參考資料，同時加深我自己對各種演算法的理解。

我不是什麼聰明的人，所以只要真的是我能理解的演算法，相信沒有經驗的初學者，
或是像我一樣程度的人，應該都能感受我的介紹相對友善(?

在這裡我將採用 C++ 作為本系列的範例 code，但是別擔心，這裡並不會使用太多只有 C++ 獨有特別寫法。

演算法競賽是什麼？

演算法競賽是種透過寫出演算法來比較的比賽。
競賽通常會有數個題目，參賽者需要寫出或設計適當的演算法和資料結構以在規範的時間、空間解決問題。

演算法是什麼？

演算法是解決問題的一個具體步驟，通常分成:

• 初始化
• 循環保持
• 終止

舉例來說，
今天你不小心打翻了可樂，你想要擦乾它，現在你考慮：
你需要節省資源，所以衛生紙要用得最少

我們要考慮的因素就要有，一張衛生紙能吸多少可樂，
並且要有效率一點，我們可以算出它吸可樂的花費時間。

我們能將這個演算法分為：

• 初始化： {
  算出 每張衛生紙吸的容量;
  用了幾張紙的變數 設為 0;
  輸入 衛生紙餘量的變數;
  輸入 可樂共有多少容量;
  }
• 循環保持： {
  每次放一張衛生紙，直到它吸飽;
  用了幾張紙的變數 加上 1;
  衛生紙餘量的變數 減上 1;
  檢查終止條件，達成則跳出，否則繼續執行循環保持;
  }
• 終止： 可樂吸完了，或是衛生紙用完了;

這三個步驟相當重要，在分析別人的演算法又或是自己設計，建議都要想想有沒有符合。

同一件事可能有許多解決方案，這時候我們透過各種方式評估哪種演算法較適當，以提高效率。
切記，各演算法沒有絕對的優劣，根據不同的場合給予適當的演算法才是根本之道

關於競賽

比賽分為實體賽與線上賽，在線上賽中，使用的系統稱為 Online Judge，簡稱 OJ，當然平時練習也用 OJ
將寫出來的解交到 OJ 上，就會得到某幾種可能的結果(只會顯示一種)：

• AC (accepted)： 提交的程式產生的解答符合系統所給的所有測試資料
• WA (wrong answer)： 產生的解答不符合系統給的測資
• CE (compilation error)： 程式碼編譯錯誤，最好比對一下編譯器是哪家版本
• RE (runtime error)： 通常是陣列超出範圍、指標指向不該指的位置、除以 0，或是遞迴過深等等的
• TLE (time limitation exceeded）： 程式運行的時間超過系統所限制的時間
• MLE (memory limitation exceeded)： 程式記憶體使用量超過系統所限制的空間

一個有趣的狀況是，有時候即使是 AC，也不見得你寫的解是正確的解答，是對方給的測試資料不夠嚴格。

參賽者需要對各種經典的資料結構和演算法有深入瞭解才能建構出合理的解題思路，也是算法競賽具體在比較的地方。

以這題來說： GCJ Kickstart Round E 2018 A Yogurt
優格可以是開胃菜，主菜或甜點的營養成分，但必須在它過期前食用，它可能會很快過期！此外，不同的優格可能在不同的日子到期。
露西喜歡優格，她剛買了 N 杯優格，但她擔心她可能無法在過期之前食用所有優格。第 i 杯優格將從今天開始起過 A_i 天過期，並且一個優格在過期當天或之後都不能食用。
儘管露西喜歡優格，但她每天只能吃至多 K 杯優格。從今天開始她可以吃掉的優格數量最多是多少？

輸入的第一行給出了測試資料的數量 T。每個測試資料以包含兩個整數 N 和 K 的一行開始，接著 N 個整數 A_i

對於每筆測試資料，輸出一行包含 Case #x：y，其中x是測試資料編號（從 1 開始），y 是露西可以消耗的最大優格杯數，如上所述。

限制：
1 ≤ T ≤ 100.
1 ≤ K ≤ N.
1 ≤ A_i ≤ 10^9, for all i.

小資料：
1 ≤ N ≤ 1000.
K = 1.

大資料：
1 ≤ N ≤ 5000.

Input

4
2 1
1 1
5 1
3 2 3 2 3
2 2
1 1
6 2
1 1 1 7 7 7
  	
Output

Case #1: 1
Case #2: 3
Case #3: 2
Case #4: 5

讀完題目後，咱們開始分析吧!
看看這些條件和環境，
先把題目會用上的變數寫上：

int const maxn = 5e3 + 10;

int N, K, a[maxn];

解法就寫在 main() 中吧
並且先輸入 T, 每次要餵 T 次測試資料：

int main()
{
  int T;
  scanf("%d", &T);
  
  while(T--) {
      :
      .
  }
  
  return 0;
}

(其中以後我們約定 : 接著下行 ., 表示這個區塊將有一些指令)

而接著可能得用上一點生活經驗，
我們會想到：是不是應該優先吃保存期限低的優格？而且當然一定要一天吃上 K 個優格
既然有靈感了，那就該嘗試一下這樣的決策是否能讓露西吃到最多的優格

總之先輸入測試資料ㄅ

scanf("%d%d", &N, &K);
for(int i = 0; i < N; i++) scanf("%d", &a[i]);

接著我們得先將所有優格按保存期限排序 (要優先吃期限最小的)

sort(a, a+N);

如果這個優格不能吃了，理論上 a[c] - day 要小於等於 0
(其中 day 表示從起點那天，總共過了多少天; a[c] 為某個優格的期限)

而露西吃了 K 個優格就該讓一天結束，那麼我們有 if(eat == K) day++;
(其中 eat 紀錄目前該天共吃了幾個優格)

綜合起來，當今天是第 day 天時，優格從小到大 a[i+0] < a[i+1] < a[i+2] < ... < a[N]
如果 a[i+0] - day <= 0 就得看是否 a[i+1] - day <= 0 依此類推... 直到否，就能將此優格吃掉！

所以我們有：

int day = 0, eat = 0;

for(int i = 0; i < N; i++) {
  if(a[i] - day <= 0) continue;
  else eat++;
  
  if(eat == K) {
      day++;
      eat = 0;
  }
}

我建議，在思考解法或是理解別人的解法的時候，應該也要從結尾往回開始去看。
也就是：

• 當露西當天吃完了 K 個，就讓今天過完？
• 將優格按照保存期限排序？

上述兩段的動機是什麼？

以下是完整解題程式碼：

#include<bits/stdc++.h>
using namespace std;

int const maxn = 5e3 + 10;

int N, K, a[maxn];

int main()
{
  int T, kase = 0;
  scanf("%d", &T);

  while(T--) {
    scanf("%d%d", &N, &K);
    for(int i = 0; i < N; i++) scanf("%d", &a[i]);

    sort(a, a+N);

    int day = 0, eat = 0;
    for(int i = 0; i < N; i++) {
      if(a[i] - day <= 0) continue;
      if(++eat % K == 0) day++;
    }

    printf("Case #%d: %d\n", ++kase, eat);
  }

  return 0;
}

關於藝術

當一件藝術品展示在外行人前，
他們頂多去問價格，或是產地，又或著問如何製造的
更進階點可能去觸碰看看，聞聞看，舔舔看(?

但藝術家會問動機
動機決定了一件藝術品該如何誕生。

如同程式，若我們作為一個藝術家去看待，
那麼就應該問動機，而不只是用了什麼演算法，記憶體分配多少，用什麼語言寫的

感謝觀看，我們明天見！